package tree.递归;

import po.TreeNode;

/**
 * @author songZiHao
 * @version 1.0.0
 * @ClassName N恢复二叉搜索树99.java
 * @Description TODO https://leetcode-cn.com/problems/recover-binary-search-tree/
 * @createTime 2021年03月25日 19:00:00
 */
public class N恢复二叉搜索树99 {

    TreeNode first = null, second = null,
    //todo 记录前一个节点
    prevNode = null;

    public void recoverTree(TreeNode root) {
        inOrder(root);
        int temp = first.val;
        first.val = second.val;
        second.val = temp;
    }

    /**
     * todo 1 6 3 4 5 2 7 8  中序时候应该是 1 2 3 4 5 6 7 9。   其中 6  3  和  5  2 都是前大后小不满足的点。第一处 错误的是6  第二处错误的是2
     * todo 中序遍历，找到比其父节点大的 和 比其父节点小的  就是两个乱序的节点
     */
    private void inOrder(TreeNode root) {
        if (root == null) {
            return;
        }
        inOrder(root.left);
        //todo 这里判断的原因是因为第一次进来的时候prevNode肯定是null，需要先设置值
        if (prevNode == null) {
            prevNode = root;
        } else {
            //todo  第一次进来的时候prevNode=6 root=3
            //todo  第二次进来的死后prevNode=5 root=2
            if (prevNode.val > root.val) {
                first = root;
                if (second == null) {
                    second = prevNode;
                }
            }
            prevNode = root;
        }
        inOrder(root.right);
    }
}
